#include <vector>
#include <algorithm>
using namespace std;
/*
 * @lc app=leetcode.cn id=300 lang=cpp
 *
 * [300] 最长递增子序列
 */

// @lc code=start
class Solution {
public:
    // 最简单的一种DP方式
    // int lengthOfLIS(vector<int>& nums) {
    //     int sz = nums.size(); int res = 1;
    //     vector<int> dp(sz, 1);
    //     dp[0] = 1;
    //     for (int i = 1; i < sz; i++) {
    //         for (int j = 0; j < i; j++) {
    //             if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
    //         }
    //         res = max(res, dp[i]);
    //     }
    //     return res;
    // }

    // dp[i]表示长度为i的最小数字
    int lengthOfLIS(vector<int>& nums) {
        int sz = nums.size();
        vector<int> dp(sz, INT_MAX);
        dp[0] = nums[0];
        for (int i = 1; i < sz; i++) {
            *lower_bound(dp.begin(), dp.end(), nums[i]) = nums[i];
        }
        for (int i = sz - 1; i >= 0; i--)
            if (dp[i] != INT_MAX) return i + 1;
        return 1;
    }
};
// @lc code=end

